package com.sinovatech.ologger.util;

public class LongTree {
	// 使用这三个数组存放数据 已经数据关系
	// 我们把要我们自己的数据ID放入数组keys中，leftChildren和rightSiblings是记录数组keys的数组ID之间关系
	// leftChildren放置的是儿子 rightSiblings存放的是其兄弟（并列的〕
	long[] keys;
	char[] leftChildren;
	char[] rightSiblings;

	// Pointer to next available slot.
	char nextIndex;

	/**
	 * 构造一个新的Tree只要提供两个参数：根数据ID 和 Tree结构的大小
	 * 
	 * @param rootKey
	 *            the value of the root node of the tree.
	 * @param initialCapacity
	 *            the maximum initial capacity of the tree
	 */
	public LongTree(long rootKey, int initialCapacity) {
		nextIndex = 2;
		keys = new long[initialCapacity + 1];
		leftChildren = new char[initialCapacity + 1];
		rightSiblings = new char[initialCapacity + 1];

		System.out.println("根接点值:" + rootKey + "树的大小:" + initialCapacity);
		// 新Tree,第一个元素当然存放我们提供的参数:根数据ID :rootKey
		// New tree, so set the fields to null at root.
		keys[1] = rootKey;
		leftChildren[1] = 0;
		rightSiblings[1] = 0;
	}

	public LongTree() {

	}

	/**
	 * Adds a child to the tree.
	 * 
	 * @param parentKey
	 *            将新的儿子加入哪个父亲下面，所以需要提供父亲的数据ID
	 * @param newKey
	 *            新的儿子本身的数据ID
	 */
	public void addChild(long parentKey, long newKey) {

		System.out.println("新插入的值:" + newKey + "他爸爸是：" + parentKey);
		// Find record for parent 检查提供的父亲是否存在
		char parentIndex = findKey(parentKey, (char) 1);
		if (parentIndex == 0)
			throw new IllegalArgumentException("Parent key " + parentKey + " not found when adding child " + newKey
					+ ".");

		if (nextIndex == keys.length) {
			int oldSize = keys.length;
			int newSize = (int) Math.ceil(oldSize * 1.5D);
			long newKeys[] = new long[newSize];
			System.arraycopy(keys, 0, newKeys, 0, oldSize);
			keys = newKeys;
			char newLeftChildren[] = new char[newSize];
			System.arraycopy(leftChildren, 0, newLeftChildren, 0, oldSize);
			leftChildren = newLeftChildren;
			char newRightSiblings[] = new char[newSize];
			System.arraycopy(rightSiblings, 0, newRightSiblings, 0, oldSize);
			rightSiblings = newRightSiblings;
		}

		// Create record for new key.加入数组 前后关系暂时设定为0
		keys[nextIndex] = newKey;
		leftChildren[nextIndex] = 0;
		rightSiblings[nextIndex] = 0;

		// Adjust references. Check to see if the parent has any children.
		if (leftChildren[parentIndex] == 0) {
			// No children, therefore make the new key the first child.
			leftChildren[parentIndex] = nextIndex;
		} else {

			/*
			 * long siblingIndex; for(siblingIndex = leftChildren[parentIndex];
			 * rightSiblings[(new Long(siblingIndex)).intValue()] != 0;
			 * siblingIndex = rightSiblings[(new
			 * Long(siblingIndex)).intValue()]); rightSiblings[(new
			 * Long(siblingIndex)).intValue()] = nextIndex;
			 */

			// The parent has children, so find the right-most child.
			// 如果这个父亲有儿子了，那么找出其最右边的儿子
			// 这样是为了将新的儿子追加在其后面，或者说最最右边
			long siblingIndex = leftChildren[parentIndex];
			while (rightSiblings[new Long(siblingIndex).intValue()] != 0) {
				siblingIndex = rightSiblings[new Long(siblingIndex).intValue()];
			}
			// Add the new entry as a sibling of that last child.
			rightSiblings[new Long(siblingIndex).intValue()] = nextIndex;
		}

		// Finally, increment nextIndex so it's ready for next add.
		nextIndex++;
	}

	public long getParent(long childKey) {
		if (keys[1] == childKey)
			return -1L;
		char childIndex = findKey(childKey, '\001');
		if (childIndex == 0)
			return -1L;
		for (char leftSiblingIndex = getLeftSiblingIndex(childIndex); leftSiblingIndex != 0; leftSiblingIndex = getLeftSiblingIndex(childIndex)) {
			childIndex = leftSiblingIndex;
		}

		for (int i = childIndex - 1; i >= 0; i--)
			if (leftChildren[i] == childIndex)
				return keys[i];

		for (int i = childIndex + 1; i <= leftChildren.length; i++)
			if (leftChildren[i] == childIndex)
				return keys[i];

		return -1L;
	}

	public long getLChild(long parentKey) {
		char parentIndex = findKey(parentKey, (char) 1);
		if (parentIndex == 0)
			return 0;
		char siblingIndex = leftChildren[parentIndex];
		if (siblingIndex == '\uFFFF' || siblingIndex == 0)
			return 0;

		return keys[siblingIndex];
	}

	public long getRChild(long parentKey) {
		char parentIndex = findKey(parentKey, (char) 1);
		if (parentIndex == 0)
			return 0;

		char siblingIndex = rightSiblings[parentIndex];

		if (siblingIndex == '\uFFFF' || siblingIndex == 0)
			return 0;

		return keys[siblingIndex];

	}

	public long getChild(long parentKey, int index) {
		char parentIndex = findKey(parentKey, '\001');
		if (parentIndex == 0)
			return -1L;
		char siblingIndex = leftChildren[parentIndex];
		if (siblingIndex == '\uFFFF')
			return -1L;
		for (int i = index; i > 0; i--) {
			siblingIndex = rightSiblings[siblingIndex];
			if (siblingIndex == 0)
				return -1L;
		}

		return keys[siblingIndex];
	}

	public int getChildCount(long parentKey) {
		int count = 0;
		char parentIndex = findKey(parentKey, '\001');
		if (parentIndex == 0)
			return 0;
		for (char siblingIndex = leftChildren[parentIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
			count++;
		}

		return count;
	}

	public long[] getChildren(long parentKey) {
		int childCount = getChildCount(parentKey);
		if (childCount == 0)
			return new long[0];
		long children[] = new long[childCount];
		int i = 0;
		char parentIndex = findKey(parentKey, '\001');
		for (char siblingIndex = leftChildren[parentIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
			children[i] = keys[siblingIndex];
			i++;
		}

		return children;
	}

	public int getIndexOfChild(long parentKey, long childKey) {
		int parentIndex = findKey(parentKey, '\001');
		int index = 0;
		char siblingIndex = leftChildren[(new Long(parentIndex)).intValue()];
		if (siblingIndex == 0)
			return -1;
		while (keys[siblingIndex] != childKey) {
			index++;
			siblingIndex = rightSiblings[siblingIndex];
			if (siblingIndex == 0)
				return -1;
		}
		return index;
	}

	public int getDepth(long key) {
		int depth[] = { 0 };
		if (findDepth(key, '\001', depth) == 0)
			return -1;
		else
			return depth[0];
	}

	public long[] getRecursiveKeys() {
		char startIndex = '\001';
		long depthKeys[] = new long[nextIndex - 1];
		depthKeys[0] = keys[startIndex];
		int cursor = 1;
		for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
			cursor = fillDepthKeys(siblingIndex, depthKeys, cursor);
		}

		return depthKeys;
	}

	public long[] getRecursiveChildren(long parentKey) {
		char startIndex = findKey(parentKey, '\001');
		long depthKeys[] = new long[nextIndex - 1];
		int cursor = 0;
		for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
			cursor = fillDepthKeys(siblingIndex, depthKeys, cursor);
		}

		long dKeys[] = new long[cursor];
		for (int i = 0; i < cursor; i++) {
			dKeys[i] = depthKeys[i];
		}

		return dKeys;
	}

	public boolean isLeaf(long key) {
		int keyIndex = findKey(key, '\001');
		if (keyIndex == 0)
			return false;
		else
			return leftChildren[keyIndex] == 0;
	}

	public long[] keys() {
		long k[] = new long[nextIndex - 1];
		for (int i = 0; i < k.length; i++) {
			k[i] = keys[i + 1];
		}

		return k;
	}

	private char findKey(long value, char startIndex) {
		if (startIndex == 0)
			return '\0';
		if (keys[startIndex] == value)
			return startIndex;
		for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
			char recursiveIndex = findKey(value, siblingIndex);
			if (recursiveIndex != 0)
				return recursiveIndex;
		}

		return '\0';
	}

	private char findDepth(long value, char startIndex, int depth[]) {
		if (startIndex == 0)
			return '\0';
		if (keys[startIndex] == value)
			return startIndex;
		for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
			depth[0]++;
			char recursiveIndex = findDepth(value, siblingIndex, depth);
			if (recursiveIndex != 0)
				return recursiveIndex;
			depth[0]--;
		}

		return '\0';
	}

	private int fillDepthKeys(char startIndex, long depthKeys[], int cursor) {
		depthKeys[cursor] = keys[startIndex];
		cursor++;
		for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
			cursor = fillDepthKeys(siblingIndex, depthKeys, cursor);
		}

		return cursor;
	}

	private char getLeftSiblingIndex(char index) {
		for (int i = index - 1; i >= 0; i--)
			if (rightSiblings[i] == index)
				return (char) i;

		for (int i = index + 1; i < rightSiblings.length; i++)
			if (rightSiblings[i] == index)
				return (char) i;

		return '\0';
	}
}
